package com.xxy.sparsearry;
/**
 * @author xxy
 * 稀疏数组的构建：
 * 1.遍历二维数组，得到有效值的个数sum
 * 2.根据sum构造一个稀疏素组int saprseArray [sum+1][3]
 * 3.将有效值存入稀疏数组
 * @create 2020 10 19 22:09
 */
public class SparseArray {
    public static void main(String[] args) {
        //创建原始数组
        int chess[][] = new int[11][11];
        chess[1][2] = 1;
        chess[2][3] = 2;
        System.out.println("原始数组");
        //原始数组的结果
        for(int [] rows:chess){
            for ( int data: rows){
                System.out.print("\t"+data);
            }
            System.out.println();
        }
        //获得原始数组中，有多少项是有效值个数sum
        int sum =0;
        for( int [] rows:chess){
            for(int data:rows){
                if(data!=0){
                    sum++;
                }
            }
        }
        //根据sum构建稀疏数组
        int sparseArray[][] = new int [sum+1][3];
        //将原数组的结构存入spareArray
        sparseArray[0][0]=chess.length;
        sparseArray[0][1]=chess[0].length;
        sparseArray[0][2]=sum;
        int count=0;//记录有效值的个数
        for(int i=0;i<chess.length;i++){
            for(int j=0;j<chess[i].length;j++){
                if(chess[i][j]!=0){
                    count++;
                    sparseArray[count][0]=i;
                    sparseArray[count][1]=j;
                    sparseArray[count][2]=chess[i][j];
                }
            }
        }
        //输出sparseArray
        for(int [] rows:sparseArray){
            for ( int data: rows){
                System.out.print("\t"+data);
            }
            System.out.println();
        }
        //根据sparseArray还原原数组
        int newChess[][] = new int[sparseArray[0][0]][sparseArray[0][0]];
        for(int i=1;i<sparseArray.length;i++){
                int row = sparseArray[i][0];
                int l = sparseArray[i][1];
                int value = sparseArray[i][2];
                newChess[row][l]=value;
        }
        //还原后的数组
        for(int [] rows:newChess){
            for ( int data: rows){
                System.out.print("\t"+data);
            }
            System.out.println();
        }
    }
}
